Section: New Results

Number and function fields

Participants : Athanasios Angelakis, Jean-Marc Couveignes, Karim Belabas.

In collaboration with Reynald Lercier, Jean-Marc Couveignes presents in [12] a randomised algorithm that on input a finite field $K$ with $q$ elements and a positive integer $d$ outputs a degree $d$ irreducible polynomial in $K\left[x\right]$. The running time is $d^{1+o\left(1\right)}\times {(logq)}^{5+o\left(1\right)}$ elementary operations. The $o\left(1\right)$ in $d^{1+o\left(1\right)}$ is a function of $d$ that tends to zero when $d$ tends to infinity. And the $o\left(1\right)$ in ${(logq)}^{5+o\left(1\right)}$ is a function of $q$ that tends to zero when $q$ tends to infinity. In particular, the complexity is quasi-linear in the degree $d$.

The book of surveys “Explicit methods in number theory. Rational points and Diophantine equations” [19] edited by K. Belabas with contributions from K. Belabas, F. Beukers, P. Gaudry, W. McCallum, B. Poonen, S. Siksek, M. Stoll and M. Watkins presents the state of the art of the use of explicit methods in arithmetic geometry to solve diophantine problems.